#!/usr/bin/python3

import random
from typing import Callable


def swap(items: list[int], a: int, b: int) -> None:
    """交换列表中，给定下标的两个元素的位置。

    Args:
        items (list[int]): 待处理列表；
        a (int): 元素a
        b (int): 元素b
    """
    items[a], items[b] = items[b], items[a]


def selectionSort(items: list[int]) -> None:
    """选择排序。

    Args:
        items (list[int]): 待排元素；
    """

    i: int = 0
    while i < len(items) - 1:
        minIndex: int = i

        j: int = i + 1
        while j < len(items):
            if items[j] < items[minIndex]:
                minIndex = j
            j += 1

        if minIndex != i:
            swap(items, minIndex, i)

        i += 1


def insertionSort(items: list[int]) -> None:
    """插入排序。

    Args:
        items (list[int]): 待排元素；
    """

    i: int = 1
    # 自前向后循环；
    while i < len(items):
        # 获取待插入元素(无序区首位)；
        itemToInsert: int = items[i]

        # 有序区末位;
        j: int = i - 1
        # 自有序区末位向前循环;
        while j >= 0:
            # 判断待插入元素是否小于当前元素;
            if itemToInsert < items[j]:  # 若是;
                # 后移元素;
                items[j + 1] = items[j]
                j -= 1
            else:  # 若否;
                break

        # 待插入元素
        items[j + 1] = itemToInsert
        i += 1


def shellSort(items: list[int]) -> None:
    """希尔排序。

    Args:
        items (list[int]): 待排元素；
    """

    gap: int = len(items) // 2

    while gap > 0:
        # 对相隔gap个位置的元素组直接插入排序;
        i: int = gap
        while i < len(items):
            itemToInsert: int = items[i]

            j: int = i - gap
            while j >= 0:
                if itemToInsert < items[j]:
                    items[j + gap] = items[j]
                    j -= gap
                else:
                    break
            items[j + gap] = itemToInsert

            i += 1

        # 缩小增量;
        gap = gap // 2


def bubbleSort(items: list[int]) -> None:
    """冒泡排序

    Args:
        items (list[int]): 待排元素；
    """
    for i in range(len(items) - 1):
        for j in range(len(items) - i - 1):
            if items[j] > items[j + 1]:
                swap(items, j, j + 1)


def quickSort(items: list[int]) -> None:
    """快速排序

    Args:
        items (list[int]): 待排元素；
    """
    quickSortHelper(items, 0, len(items) - 1)


def partition(items: list[int], low: int, high: int) -> int:
    """快速排序划分函数。

    Args:
        items (list[int]): 待排列表；
        low (int): 低位索引；
        high (int): 高位索引；

    Returns:
        int: _description_
    """
    i: int = low
    j: int = high

    while i < j:
        # 将地位取做枢纽值，暂存；
        povit: int = items[i]

        # 自高位向低位，找到比枢纽值小的值；
        while items[j] >= povit and i < j:
            j -= 1

        # 将其存储到低位；
        items[i] = items[j]

        # 自高位向低位，找到比枢纽值大的值；
        while items[i] <= povit and i < j:
            i += 1

        # 将其存储到高位；
        items[j] = items[i]

    # 枢纽值到位；
    items[i] = povit

    return i


def quickSortHelper(items: list[int], p: int, r: int) -> None:
    """快速排序的辅助函数。

    Args:
        items (list[int]): 待排元素；
        p (int): 起始值；
        r (int): 结束值；
    """
    if p < r:
        i: int = partition(items, p, r)
        quickSortHelper(items, p, i - 1)
        quickSortHelper(items, i + 1, r)


def mergeSort(items: list[int]) -> None:
    """归并排序。

    Args:
        items (list[int]): 待排元素；
    """

    copyBuffer = [0] * len(items)
    mergeSortHelper(items, copyBuffer, 0, len(items) - 1)


def mergeSortHelper(
    items: list[int], copyBuffer: list[int], low: int, high: int
) -> None:
    """归并排序的辅助函数。

    Args:
        items (list[int]): 待排元素；
        copyBuffer (list[int]): 临时空间；
        low (int): 低位索引；
        high (int): 高位索引；
    """

    if low < high:
        middle = (low + high) // 2
        mergeSortHelper(items, copyBuffer, low, middle)
        mergeSortHelper(items, copyBuffer, middle + 1, high)
        meger(items, copyBuffer, low, middle, high)


def meger(
    items: list[int], copyBuffer: list[int], low: int, middle: int, high: int
) -> None:
    """归并排序的归并函数。

    Args:
        items (list[int]): 待排元素；
        copyBuffer (list[int]):  临时空间；
        low (int): 低位索引；
        middle (int): 中位索引；
        high (int): 高位索引；
    """

    # 用于遍历前段子表；
    i: int = low
    # 用于遍历后段子表；
    j: int = middle + 1

    for k in range(low, high + 1):
        if i > middle:  # 前段子表已用尽；
            # 复制后段元素；
            copyBuffer[k] = items[j]
            j += 1
        elif j > high:  # 后段子表已用尽；
            # 复制前段元素；
            copyBuffer[k] = items[i]
            i += 1
        elif items[i] < items[j]:  # 前段元素较小；
            # 复制前段元素；
            copyBuffer[k] = items[i]
            i += 1
        else:  # 前段元素较小；
            # 复制前段元素；
            copyBuffer[k] = items[j]
            j += 1

    for k in range(low, high + 1):
        items[k] = copyBuffer[k]


def countingSort(nums: list[int]) -> None:
    """计数排序。
    计数排序简单实现。
    Args:
        nums (list[int]): 待排序列；
    """

    # 统计数组最大元素 m
    m: int = 0
    for num in nums:
        m = max(m, num)

    # 统计各数字的出现次数
    # counter[num] 代表 num 的出现次数
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1

    # 遍历 counter ，将各元素填入原数组 nums
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1


def digit(num: int, exp: int) -> int:
    """获取元素 num 的第 k 位，其中 exp = 10^(k-1)"""
    # 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
    return (num // exp) % 10


def counting_sort_digit(nums: list[int], exp: int):
    """计数排序（根据 nums 第 k 位排序）"""
    # 十进制的位范围为 0~9 ，因此需要长度为 10 的桶
    counter = [0] * 10
    n = len(nums)
    # 统计 0~9 各数字的出现次数
    for i in range(n):
        d = digit(nums[i], exp)  # 获取 nums[i] 第 k 位，记为 d
        counter[d] += 1  # 统计数字 d 的出现次数
    # 求前缀和，将“出现个数”转换为“数组索引”
    for i in range(1, 10):
        counter[i] += counter[i - 1]
    # 倒序遍历，根据桶内统计结果，将各元素填入 res
    res = [0] * n
    for i in range(n - 1, -1, -1):
        d = digit(nums[i], exp)
        j = counter[d] - 1  # 获取 d 在数组中的索引 j
        res[j] = nums[i]  # 将当前元素填入索引 j
        counter[d] -= 1  # 将 d 的数量减 1
    # 使用结果覆盖原数组 nums
    for i in range(n):
        nums[i] = res[i]


def radix_sort(nums: list[int]):
    """基数排序"""
    # 获取数组的最大元素，用于判断最大位数
    m = max(nums)
    # 按照从低位到高位的顺序遍历
    exp = 1
    while exp <= m:
        # 对数组元素的第 k 位执行计数排序
        # k = 1 -> exp = 1
        # k = 2 -> exp = 10
        # 即 exp = 10^(k-1)
        counting_sort_digit(nums, exp)
        exp *= 10


def main(size: int = 10, sort: Callable = quickSort):
    """主函数。

    Args:
        size (int, optional): 待排元素个数. Defaults to 10.
        sort (Callable, optional): 排序函数. Defaults to quickSort.
    """

    lyst: int = []
    for count in range(size):
        lyst.append(random.randint(1, 99))

    print(lyst)
    sort(lyst)
    print(lyst)


if __name__ == "__main__":
    main(sort=radix_sort)
